package org.example;

import java.util.Arrays;

public class Test1 {
    public String minWindow1(String s, String t) {
        int left = 0, right = 0;
        int n1 = s.length(), n2 = t.length();
        int count = 0, type1 = 0;
        int[] hash1 = new int[58];
        for (char c : t.toCharArray()) {
            if (hash1[c-'A'] == 0) type1++;
            hash1[c-'A']++;
        }
        int[] hash2 = new int[58];
        int type2 = 0, ret = 100001,start = 0,end = 0;
        while (right < n1) {
            while (right < n1 && (type2 < type1 || count < n2)) {
                char tmp = s.charAt(right);
                hash2[tmp-'A']++;

                if (hash1[tmp-'A'] > 0) {
                    if (hash2[tmp-'A'] == 1) type2++;
                    count++;
                }
                right++;
            }
            while (left < right && type2 >= type1) {
                if (count > n2 && right-left < ret) {
                    ret = right - left;
                    start = left;
                    end = right;
                }
                int[] arr = Arrays.copyOf(hash1,58);
                char tmp = s.charAt(left);
                hash2[tmp-'A']--;
                if (--arr[tmp-'A'] >= 0) {
                    if (hash2[tmp-'A'] == 0) type2--;
                    count--;
                }
                left++;
            }
            while (left < right && hash1[s.charAt(left)-'A'] == 0) left++;
        }
        return end > start ? s.substring(start,end) : "";
    }

    public String minWindow(String s, String t) {
        int left = 0, right = 0;
        int n1 = s.length(), n2 = t.length();
        int count = 0; // 当前匹配的字符数
        int type1 = 0; // t 中唯一字符的个数
        int[] hash1 = new int[58]; // 记录 t 中字符的频率

        // 初始化 t 的字符频率和类型数量
        for (char c : t.toCharArray()) {
            if (hash1[c - 'A'] == 0) type1++;
            hash1[c - 'A']++;
        }

        int[] hash2 = new int[58]; // 当前窗口中字符的频率
        int type2 = 0; // 当前窗口中与 t 匹配的字符类型数
        int minLen = Integer.MAX_VALUE; // 最小窗口长度
        int start = 0; // 最小窗口的起始位置

        while (right < n1) {
            // 扩展右边界
            char rightChar = s.charAt(right);
            hash2[rightChar - 'A']++;

            // 如果该字符在 t 中，并且当前窗口的频率匹配，更新 type2
            if (hash1[rightChar - 'A'] > 0 && hash2[rightChar - 'A'] == hash1[rightChar - 'A']) {
                type2++;
            }
            if (hash1[rightChar - 'A'] > 0) {
                count++;
            }
            right++;

            // 收缩左边界，确保窗口仍然满足条件
            while (type2 == type1) {
                // 更新最小窗口
                if (right - left < minLen) {
                    minLen = right - left;
                    start = left;
                }

                char leftChar = s.charAt(left);
                hash2[leftChar - 'A']--;

                // 如果该字符在 t 中，并且移出窗口导致频率不再匹配，更新 type2
                if (hash1[leftChar - 'A'] > 0 && hash2[leftChar - 'A'] < hash1[leftChar - 'A']) {
                    type2--;
                }
                if (hash1[leftChar - 'A'] > 0) {
                    count--;
                }
                left++;
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }

    public static void main(String[] args) {
        Test1 test1 = new Test1();
        String s = "a", t = "aa";
        String ret = test1.minWindow(s,t);
        System.out.println(ret);
        System.out.println(444);
    }
}
